{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum White Tiles After Covering With Carpets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumWhiteTiles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #用地毯覆盖后的最少白色砖块"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从<strong>&nbsp;0</strong>&nbsp;开始的 <strong>二进制</strong>&nbsp;字符串&nbsp;<code>floor</code>&nbsp;，它表示地板上砖块的颜色。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>floor[i] = '0'</code>&nbsp;表示地板上第&nbsp;<code>i</code>&nbsp;块砖块的颜色是 <strong>黑色</strong>&nbsp;。</li>\n",
    "\t<li><code>floor[i] = '1'</code>&nbsp;表示地板上第&nbsp;<code>i</code>&nbsp;块砖块的颜色是 <strong>白色</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>同时给你&nbsp;<code>numCarpets</code> 和&nbsp;<code>carpetLen</code>&nbsp;。你有&nbsp;<code>numCarpets</code>&nbsp;条&nbsp;<strong>黑色</strong>&nbsp;的地毯，每一条&nbsp;<strong>黑色</strong>&nbsp;的地毯长度都为&nbsp;<code>carpetLen</code>&nbsp;块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 <strong>白色</strong>&nbsp;砖块的数目 <strong>最小</strong>&nbsp;。地毯相互之间可以覆盖。</p>\n",
    "\n",
    "<p>请你返回没被覆盖的白色砖块的 <strong>最少</strong>&nbsp;数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/02/10/ex1-1.png\" style=\"width: 400px; height: 73px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>floor = \"10110101\", numCarpets = 2, carpetLen = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "上图展示了剩余 2 块白色砖块的方案。\n",
    "没有其他方案可以使未被覆盖的白色砖块少于 2 块。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/02/10/ex2.png\" style=\"width: 353px; height: 123px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>floor = \"11111\", numCarpets = 2, carpetLen = 3\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>\n",
    "上图展示了所有白色砖块都被覆盖的一种方案。\n",
    "注意，地毯相互之间可以覆盖。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= carpetLen &lt;= floor.length &lt;= 1000</code></li>\n",
    "\t<li><code>floor[i]</code> 要么是&nbsp;<code>'0'</code>&nbsp;，要么是&nbsp;<code>'1'</code>&nbsp;。</li>\n",
    "\t<li><code>1 &lt;= numCarpets &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-white-tiles-after-covering-with-carpets](https://leetcode.cn/problems/minimum-white-tiles-after-covering-with-carpets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-white-tiles-after-covering-with-carpets](https://leetcode.cn/problems/minimum-white-tiles-after-covering-with-carpets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"10110101\"\\n2\\n2', '\"11111\"\\n2\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        if numCarpets * carpetLen >= len(floor):\n",
    "            return 0\n",
    "        \n",
    "        # dp[i][j] represent the first i capets on first j positions\n",
    "        dp1 = [0] * len(floor)\n",
    "        dp2 = [0] * len(floor)\n",
    "\n",
    "        dp1[0] += (floor[0] == \"1\")\n",
    "        for j in range(1, len(floor)):\n",
    "            dp1[j] = dp1[j-1] + (floor[j] == \"1\")\n",
    "        \n",
    "        for i in range(1, numCarpets + 1):\n",
    "            dp2[i * carpetLen - 1] = 0\n",
    "            for j in range(i * carpetLen, len(floor)):\n",
    "                dp2[j] = min(dp2[j-1] + (floor[j] == \"1\"), dp1[j-carpetLen])\n",
    "            dp1, dp2 = dp2, dp1\n",
    "        \n",
    "        return dp1[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        floor = list(map(int, floor))\n",
    "        state = list(accumulate(floor))\n",
    "        state1 = [0]*len(floor)\n",
    "        for _ in range(numCarpets):\n",
    "            last = 0\n",
    "            for i, color in enumerate(floor):\n",
    "                if color:\n",
    "                    state1[i] = last = min(last + 1, state[i-carpetLen] if i >= carpetLen else 0)\n",
    "                else:\n",
    "                    state1[i] = last\n",
    "            state, state1 = state1, state \n",
    "        return state[-1]\n",
    "        \n",
    "        # W[n][c] = W[n-1][c] if floor[n] == '0'\n",
    "        #   = min(W[n-1][c]+1, W[n-len][c-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        a = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            a[i+1] = a[i] + int(floor[i])\n",
    "        for i in range(carpetLen, n+1):\n",
    "            a[i-carpetLen] = a[i] - a[i-carpetLen]\n",
    "        for i in range(n - carpetLen + 1, n):\n",
    "            a[i] = a[n] - a[i]\n",
    "        dp = a[:n]\n",
    "        for k in range(1, numCarpets):\n",
    "            if k * carpetLen >= n:\n",
    "                break\n",
    "            x = 0\n",
    "            temp = [0] * n\n",
    "            for i in range(k * carpetLen, n):\n",
    "                x = max(x, dp[i-carpetLen])\n",
    "                temp[i] = x + a[i]\n",
    "            dp = temp\n",
    "        return floor.count('1') - max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        \n",
    "        if carpetLen * numCarpets >= len(floor):\n",
    "            return 0\n",
    "        \n",
    "        dp = [[0] * (len(floor)) for _ in range(numCarpets + 1)]\n",
    "        # numcaptes + 1 rows, len(floor) columns, indicating each position\n",
    "        dp[0][0] += (floor[0] == \"1\")\n",
    "        for j in range(1, len(floor)):\n",
    "            dp[0][j] = dp[0][j-1] + (floor[j] == \"1\")\n",
    "    \n",
    "        for i in range(1, numCarpets + 1):\n",
    "            for j in range(carpetLen * i, len(floor)):\n",
    "                dp[i][j] = min(dp[i - 1][j - carpetLen], dp[i][j-1] + (floor[j] == \"1\"))\n",
    "                \n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        if carpetLen * numCarpets >= n: \n",
    "            return 0\n",
    "        f = [[0] * (numCarpets + 1) for i in range(n + 1)]\n",
    "        cnt = [0] * (n + 1)\n",
    "       \n",
    "        for i in range(1, n + 1):\n",
    "            cnt[i] = cnt[i - 1] + (floor[i - 1] == '1')\n",
    "            for c in range(1, numCarpets + 1):\n",
    "                f[i][c] = max(f[i - 1][c], (f[i - carpetLen][c - 1] if i >= carpetLen else 0) + (cnt[i] - cnt[max(0, i - carpetLen)]))\n",
    "        return cnt[n] - f[n][numCarpets]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        sLen = len(floor)\n",
    "        ans = sLen\n",
    "        cnt = [0 for _ in range(sLen+1)]\n",
    "        for i in range(1, sLen+1):\n",
    "            if floor[i-1] == '1':\n",
    "                cnt[i] = cnt[i-1]+1\n",
    "            else:\n",
    "                cnt[i] = cnt[i-1]\n",
    "\n",
    "        if numCarpets*carpetLen >= sLen:\n",
    "            return 0\n",
    "\n",
    "        def Count(start, end):\n",
    "            return cnt[end] - cnt[start]\n",
    "        \n",
    "        dp = [[0 for _ in range(numCarpets+1)] for _ in range(sLen)]\n",
    "        for i in range(1, numCarpets+1):\n",
    "            if floor[0] == '1':\n",
    "                dp[0][i] = 1\n",
    "            else:\n",
    "                dp[0][i] = 0\n",
    "\n",
    "        for i in range(1, sLen):\n",
    "            for j in range(1, numCarpets+1):\n",
    "                if i < carpetLen:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                    if floor[i] == '1':\n",
    "                        dp[i][j] += 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-carpetLen][j-1] + Count(i-carpetLen+1, i+1))\n",
    "\n",
    "        return Count(0, sLen) - dp[sLen-1][numCarpets]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        m, n = numCarpets+1, len(floor)\n",
    "        ## f[i][j]: min visible when covering floor[:j+1] with i carpets\n",
    "        f = [[0]*n for _ in range(m)]\n",
    "        f[0][0] = int(floor[0] == '1')\n",
    "        # for i in range(1, m):  f[i][0] = 0\n",
    "        for j in range(1, n):\n",
    "            f[0][j] = f[0][j-1] + int(floor[j] == '1')\n",
    "            for i in range(1, m):\n",
    "                if floor[j] == '0':\n",
    "                    f[i][j] = f[i][j-1]\n",
    "                else:\n",
    "                    g = f[i-1][j-carpetLen] if j >= carpetLen else 0\n",
    "                    f[i][j] = min(g, f[i][j-1] + 1)\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        m, n = len(floor), numCarpets+1\n",
    "        f = [[0]*n for _ in range(m)]\n",
    "        f[0][0] = int(floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            f[i][0] = f[i-1][0] + int(floor[i] == '1')\n",
    "        # for j in range(1, n):\n",
    "        #     f[0][j] = 0\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                f[i][j] = f[i][j-1]\n",
    "                if floor[i] == '0':\n",
    "                    f[i][j] = min(f[i][j], f[i-1][j])\n",
    "                else:\n",
    "                    f[i][j] = min(f[i][j], f[i-carpetLen][j-1] if i >= carpetLen else 0)\n",
    "                    f[i][j] = min(f[i][j], f[i-1][j] + 1)\n",
    "\n",
    "        return f[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "\n",
    "        n = len(floor)\n",
    "        cnt = floor.count('1')\n",
    "        dp = [[0] * (numCarpets + 1) for _ in range(n + 1)]\n",
    "        if numCarpets * carpetLen >= n:\n",
    "            return 0\n",
    "        a = list(map(int, floor))\n",
    "        pres = list(accumulate(a, initial=0))\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, numCarpets + 1):\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                if i - carpetLen >= 0:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - carpetLen][j - 1] + pres[i] - pres[i - carpetLen])\n",
    "        return cnt - dp[n][numCarpets]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if numCarpets * carpetLen >= m: return 0\n",
    "        f = [[0] * m for _ in range(numCarpets + 1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, numCarpets + 1):\n",
    "            for j in range(i * carpetLen, m):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        return f[numCarpets][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >= m: return 0  # 剪枝\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, n + 1):\n",
    "            # j < carpetLen * i 的 f[i][j] 均为 0\n",
    "            for j in range(carpetLen * i, m):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        return f[n][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        #copy 0x3\n",
    "        n = numCarpets\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >=m:\n",
    "            return 0\n",
    "        f= [[0]*m for _ in range(n+1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1,m):\n",
    "            f[0][i] = f[0][i-1] + (floor[i]=='1')#必须有括号\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            for j in range(carpetLen*i,m):\n",
    "                f[i][j] = min(f[i][j-1]+ (floor[j]=='1'),f[i-1][j-carpetLen])\n",
    "        \n",
    "        return f[n][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if numCarpets * carpetLen >= m:\n",
    "            return 0\n",
    "        dp = [[0] * m for _ in range(numCarpets + 1)]\n",
    "        dp[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            dp[0][i] = dp[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, numCarpets + 1):\n",
    "            for j in range(carpetLen * i, m):\n",
    "                dp[i][j] = min(dp[i][j - 1] + (floor[j] == '1'), dp[i - 1][j - carpetLen])\n",
    "        return dp[numCarpets][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if m <= numCarpets*carpetLen:\n",
    "            return 0\n",
    "        dp = [[0]*m for _ in range(numCarpets+1)]\n",
    "        dp[0][0] = 1 if floor[0]=='1' else 0\n",
    "        for i in range(1,m):\n",
    "            dp[0][i] = dp[0][i-1] + int(floor[i] == '1')\n",
    "        #print(dp[0])\n",
    "        for i in range(1,numCarpets+1):\n",
    "            for j in range(i*carpetLen,m): \n",
    "                    dp[i][j] = min(dp[i][j-1]+int(floor[j]=='1'),\n",
    "                        dp[i-1][j-carpetLen])\n",
    "            #print(dp[i])\n",
    "        return dp[-1][-1]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        ans, n = 0, len(floor)\n",
    "        if numCarpets * carpetLen >= n:\n",
    "            return ans\n",
    "        dp = [[0] * n for _ in range(numCarpets + 1)]\n",
    "        dp[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = dp[0][i-1] + (floor[i] == '1')\n",
    "        for i in range(1, numCarpets+1):\n",
    "            for j in range(carpetLen * i, n):            \n",
    "                dp[i][j] = min(dp[i][j-1] + (floor[j] == '1'), dp[i-1][j-carpetLen])\n",
    "        return dp[numCarpets][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >= m: return 0  # 剪枝\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, n + 1):\n",
    "            # j < carpetLen * i 的 f[i][j] 均为 0\n",
    "            for j in range(carpetLen * i, m):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        return f[n][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        flist = [int(c) for c in floor]\n",
    "        n = len(flist)\n",
    "        if numCarpets*carpetLen>=n: return 0\n",
    "        pre = list(accumulate(flist, initial=0))\n",
    "        dp = [[0]*(n+1) for _ in range(numCarpets+1)]\n",
    "        #  dp[i][j] 表示用了最多i个地毯后，[0,j)仍然可见的最小白色砖块数量\n",
    "        for j in range(n+1):\n",
    "            dp[0][j] = pre[j]\n",
    "        for i in range(1,numCarpets+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = dp[i][j-1] + (1 if flist[j-1] == 1 else 0)\n",
    "                dp[i][j] = min(dp[i][j], dp[i-1][max(j-carpetLen,0)])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        #copy 0x3\n",
    "        n = numCarpets\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >=m:\n",
    "            return 0\n",
    "        f= [[0]*m for _ in range(n+1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1,m):\n",
    "            f[0][i] = f[0][i-1] + (floor[i]=='1')\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            for j in range(carpetLen*i,m):\n",
    "                f[i][j] = min(f[i][j-1]+ (floor[j]=='1'),f[i-1][j-carpetLen])\n",
    "        \n",
    "        return f[n][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\r\n",
    "f[i][j] 表示用 i 条地毯覆盖前 j 块板砖时，没被覆盖的白色砖块的最少数目。\r\n",
    "\r\n",
    "'''\r\n",
    "class Solution:\r\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\r\n",
    "        m = len(floor)\r\n",
    "        if n * carpetLen >= m: return 0  # 剪枝\r\n",
    "        f = [[0] * m for _ in range(n + 1)]\r\n",
    "        f[0][0] = (floor[0] == '1')\r\n",
    "        for i in range(1, m):\r\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            # j < carpetLen * i 的 f[i][j] 均为 0\r\n",
    "            for j in range(carpetLen * i, m):\r\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\r\n",
    "        return f[n][-1]\r\n",
    "        \r\n",
    "    # 用滚动数组压缩掉第一维\r\n",
    "    def minimumWhiteTiles2(self, floor: str, n: int, carpetLen: int) -> int:\r\n",
    "        m = len(floor)\r\n",
    "        if n * carpetLen >= m: return 0  # 剪枝\r\n",
    "        pre, f = [0] * m, [0] * m\r\n",
    "        pre[0] = (floor[0] == '1')\r\n",
    "        for i in range(1, m):\r\n",
    "            pre[i] = pre[i - 1] + (floor[i] == '1')\r\n",
    "        for i in range(1, n + 1):\r\n",
    "            # j < carpetLen * i 的 f[i][j] 均为 0\r\n",
    "            f[carpetLen * i - 1] = 0\r\n",
    "            for j in range(carpetLen * i, m):\r\n",
    "                f[j] = min(f[j - 1] + (floor[j] == '1'), pre[j - carpetLen])\r\n",
    "            pre, f = f, pre\r\n",
    "        return pre[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >= m: return 0  # 剪枝\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, n + 1):\n",
    "            # j < carpetLen * i 的 f[i][j] 均为 0\n",
    "            for j in range(carpetLen * i, m):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        return f[n][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >= m: return 0  # 剪枝\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, n + 1):\n",
    "            # j < carpetLen * i 的 f[i][j] 均为 0\n",
    "            for j in range(carpetLen * i, m):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        return f[n][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >= m: return 0  # 剪枝\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, n + 1):\n",
    "            # j < carpetLen * i 的 f[i][j] 均为 0\n",
    "            for j in range(carpetLen * i, m):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        return f[n][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >= m: return 0 # 剪枝\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "\n",
    "        for i in range(1, m):\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, n + 1):\n",
    "            # j < carpetLen * i 的f[i][j] 均为0\n",
    "            for j in range(carpetLen * i, m):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        return f[n][-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >= m: return 0  # 剪枝\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, n + 1):\n",
    "            # j < carpetLen * i 的 f[i][j] 均为 0\n",
    "            for j in range(carpetLen * i, m):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        return f[n][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        flist = [int(c) for c in floor]\n",
    "        n = len(flist)\n",
    "        if numCarpets*carpetLen>=n: return 0\n",
    "        pre = list(accumulate(flist, initial=0))\n",
    "        dp = [[0]*(n+1) for _ in range(numCarpets+1)]\n",
    "        #  dp[i][j] 表示用了最多i个地毯后，[0,j)仍然可见的最小白色砖块数量\n",
    "        #  状态转移就是，在j位置是否用地毯\n",
    "        for j in range(n+1):\n",
    "            dp[0][j] = pre[j]\n",
    "        for i in range(1,numCarpets+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = dp[i][j-1] + (1 if flist[j-1] == 1 else 0)\n",
    "                dp[i][j] = min(dp[i][j], dp[i-1][max(j-carpetLen,0)])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if numCarpets * carpetLen >= m: return 0\n",
    "        \n",
    "        # dp[i][j] 表示用 i 条地毯覆盖前 j 块板砖时没被覆盖的白色砖块的最少数目\n",
    "        dp = [[0] * m for _ in range(numCarpets+1)]\n",
    "        dp[0][0] = floor[0] == \"1\"\n",
    "        \n",
    "        for j in range(1, m):\n",
    "            dp[0][j] = dp[0][j-1] + (floor[j] == \"1\")\n",
    "        \n",
    "        for i in range(1, numCarpets+1):\n",
    "            # j < carpetLen * i 的 dp[i][j] 均为 0\n",
    "            for j in range(carpetLen*i, m):\n",
    "                dp[i][j] = min(dp[i][j-1]+(floor[j]==\"1\"), dp[i-1][j-carpetLen])\n",
    "        \n",
    "        return dp[numCarpets][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        if numCarpets * carpetLen >= len(floor):\n",
    "            return 0\n",
    "        \n",
    "        # dp[i][j] represent the first i capets on first j positions\n",
    "        dp = [[0] * len(floor) for _ in range(numCarpets + 1)] \n",
    "\n",
    "        dp[0][0] += (floor[0][0] == \"1\")\n",
    "        for j in range(1, len(floor)):\n",
    "            dp[0][j] = dp[0][j-1] + (floor[j] == \"1\")\n",
    "        \n",
    "        for i in range(1, numCarpets + 1):\n",
    "            for j in range(i * carpetLen, len(floor)):\n",
    "                dp[i][j] = min(dp[i][j-1] + (floor[j] == \"1\"), dp[i-1][j-carpetLen])\n",
    "        \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\n",
    "        m = len(floor)\n",
    "        if n * carpetLen >= m: return 0  # 剪枝\n",
    "        f = [[0] * m for _ in range(n + 1)]\n",
    "        f[0][0] = (floor[0] == '1')\n",
    "        for i in range(1, m):\n",
    "            f[0][i] = f[0][i - 1] + (floor[i] == '1')\n",
    "        for i in range(1, n + 1):\n",
    "            # j < carpetLen * i 的 f[i][j] 均为 0\n",
    "            for j in range(carpetLen * i, m):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        return f[n][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumWhiteTiles(self, floor: str, n: int, carpetLen: int) -> int:\r\n",
    "        m = len(floor)\r\n",
    "        if n * carpetLen >= len(floor): return 0\r\n",
    "        dp = [[0]* m for _ in range(n+1)]\r\n",
    "        dp[0][0] = (floor[0][0] == '1')\r\n",
    "        for i in range(1,m):\r\n",
    "            dp[0][i] = dp[0][i-1] + (floor[i] == '1')\r\n",
    "        for i in range(1,n+1):\r\n",
    "            for j in range(carpetLen * i, m):\r\n",
    "                dp[i][j] = min(dp[i][j-1]+ (floor[j] == '1'), dp[i-1][j-carpetLen])\r\n",
    "        return dp[n][-1]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        # O(mn) dp\n",
    "        m = len(floor)\n",
    "        if numCarpets*carpetLen >= m: return 0\n",
    "        s = [0]*(m+1)   # 前缀和数组\n",
    "        for i, num_str in enumerate(floor):\n",
    "            s[i+1] = s[i] + (num_str == \"1\")\n",
    "        # dp[i][j]  前i块用j个carpets覆盖留下的最小数目\n",
    "        dp = [[inf]*(numCarpets+1) for _ in range(m+1)] \n",
    "        # dp[0][:] = 0   dp[i][0] = s[i]\n",
    "        for i in range(m+1):\n",
    "            dp[i][0] = s[i]\n",
    "        for j in range(numCarpets+1):\n",
    "            dp[0][j] = 0\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, numCarpets+1): \n",
    "                if i - carpetLen < 0:\n",
    "                    dp[i][j] = 0\n",
    "                    continue\n",
    "                dp[i][j] = min(dp[i-1][j] + (floor[i-1] == \"1\"), dp[i-carpetLen][j-1])\n",
    "        return dp[m][numCarpets]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n=len(floor)\n",
    "        if numCarpets*carpetLen>n:\n",
    "            return 0\n",
    "        dp=[[0]*(n) for _ in range(numCarpets+1)]\n",
    "\n",
    "        dp[0][0]=int(floor[0]==\"1\")\n",
    "        for i in range(1,n):\n",
    "            dp[0][i]=dp[0][i-1]+int(floor[i]==\"1\")\n",
    "\n",
    "        for i in range(1,numCarpets+1):\n",
    "            for j in range(i*carpetLen,n):\n",
    "                dp[i][j]=min(dp[i][j-1]+int(floor[j]==\"1\"),dp[i-1][j-carpetLen] )\n",
    "      #  print(dp)\n",
    "        return dp[numCarpets][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        m, n = numCarpets, len(floor)\n",
    "        dp = [[0] * n for _ in range(m + 1)]\n",
    "        for j in range(n):\n",
    "            if not j:\n",
    "                dp[0][0] = int(floor[j])\n",
    "            else:\n",
    "                dp[0][j] = dp[0][j - 1] + int(floor[j])\n",
    "        \n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(n):\n",
    "                if j >= carpetLen:\n",
    "                    dp[i][j] = min(dp[i][j - 1] + int(floor[j]), dp[i - 1][j - carpetLen])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor) \n",
    "        dp = [[float('inf')] * (numCarpets+1) for _ in range(n+1)]\n",
    "        for j in range(numCarpets+1):\n",
    "            dp[0][j] = 0 \n",
    "        for i in range(1, n+1):\n",
    "            for j in range(numCarpets+1):\n",
    "                dp[i][j] = dp[i-1][j] + int(floor[i-1] == '1')\n",
    "                if j >= 1:\n",
    "                    dp[i][j] = min(dp[i][j], dp[max(i-carpetLen, 0)][j-1])\n",
    "        #print(dp) \n",
    "        return dp[n][numCarpets]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        flist = [int(c) for c in floor]\n",
    "        n = len(flist)\n",
    "        # if numCarpets*carpetLen>=n: return 0\n",
    "        pre = list(accumulate(flist, initial=0))\n",
    "        dp = [[0]*(n+1) for _ in range(numCarpets+1)]\n",
    "        #  dp[i][j] 表示用了最多i个地毯后，[0,j)仍然可见的最小白色砖块数量\n",
    "        for j in range(n+1):\n",
    "            dp[0][j] = pre[j]\n",
    "        for i in range(1,numCarpets+1):\n",
    "            for j in range(1, n+1):\n",
    "                dp[i][j] = dp[i][j-1] + (1 if flist[j-1] == 1 else 0)\n",
    "                dp[i][j] = min(dp[i][j], dp[i-1][max(j-carpetLen,0)])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        cnt = floor.count('1')\n",
    "        for i, x in enumerate(floor):\n",
    "            pre_sum[i + 1] = pre_sum[i] + (x == '1') \n",
    "        print(pre_sum)\n",
    "        f = [[0] * n for _ in range(numCarpets + 1)]\n",
    "        for i in range(n):\n",
    "            f[0][i] = pre_sum[i + 1]\n",
    "        for i in range(1, numCarpets + 1):\n",
    "            for j in range(carpetLen * i, n):\n",
    "                f[i][j] = min(f[i][j - 1] + (floor[j] == '1'), f[i - 1][j - carpetLen])\n",
    "        #print(f)\n",
    "        return f[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "直接dp起手\n",
    "状态定义:\n",
    "题目要求什么就定义什么，需要把握住变量的关系\n",
    "一个是砖块长度，一个是地毯数量\n",
    "f[i][j]就是用i块地毯覆盖前j块砖块后，没有被覆盖的白色砖块的最少数目\n",
    "\n",
    "状态转移:\n",
    "考虑是否使用第i条地毯覆盖第j块板砖\n",
    "不使用: f[i][j] = f[i][j-1] + (floor[j] == 1)\n",
    "使用: f[i][j] = f[i-1][j - carpetLen]\n",
    "两者使用最小值即可\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        f = [[0] * n for _ in range(numCarpets + 1)]\n",
    "        cnt1 = 0\n",
    "        for i in range(n):\n",
    "            cnt1 += (floor[i] == '1')\n",
    "            f[0][i] = cnt1\n",
    "        for i in range(1, numCarpets + 1):\n",
    "            for j in range(1, n):\n",
    "                # 不使用\n",
    "                f[i][j] = f[i][j-1] + (floor[j] == '1') \n",
    "                if j >= carpetLen:\n",
    "                    f[i][j] = min(f[i][j], f[i-1][j - carpetLen])\n",
    "                else:\n",
    "                    f[i][j] = 0\n",
    "        # print(f)\n",
    "        return f[numCarpets][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        floor = '0' + floor\n",
    "        n = len(floor)\n",
    "        dp = [[0] * (numCarpets + 1) for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            dp[i][0] = int(floor[i]) + dp[i-1][0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, numCarpets + 1):\n",
    "                dp[i][j] = dp[i-1][j] + int(floor[i])\n",
    "                p = max(i - carpetLen, 0)\n",
    "                dp[i][j] = min(dp[i][j], dp[p][j-1])\n",
    "        return dp[-1][-1]\n",
    "s = Solution()\n",
    "s.minimumWhiteTiles('10110101',2,2)\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        f = [[0] * (numCarpets + 1) for i in range(n + 1)]\n",
    "        cnt = [0] * (n + 1)\n",
    "       \n",
    "        for i in range(1, n + 1):\n",
    "            cnt[i] = cnt[i - 1] + (floor[i - 1] == '1')\n",
    "            for c in range(1, numCarpets + 1):\n",
    "                f[i][c] = max(f[i - 1][c], (f[i - carpetLen][c - 1] if i >= carpetLen else 0) + (cnt[i] - cnt[max(0, i - carpetLen)]))\n",
    "        return cnt[n] - f[n][numCarpets]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        f = [[0] * (numCarpets + 1) for i in range(n + 1)]\n",
    "        cnt = [0] * (n + 1)\n",
    "       \n",
    "        for i in range(1, n + 1):\n",
    "            cnt[i] = cnt[i - 1] + (floor[i - 1] == '1')\n",
    "            # f[i][]\n",
    "            for c in range(1, numCarpets + 1):\n",
    "                # f[i][c] = f[i - 1][c - 1]\n",
    "                f[i][c] = max(f[i - 1][c], (f[i - carpetLen][c - 1] if i >= carpetLen else 0) + (cnt[i] - cnt[max(0, i - carpetLen)]))\n",
    "        \n",
    "        return cnt[n] - f[n][numCarpets]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        #看了提示\n",
    "        #dp solution\n",
    "        #dp[i][j]表示i位置用j个黑砖能覆盖多少\n",
    "        #dp[i][j]肯定跟三个东西有关\n",
    "        #dp[i-1][j]\n",
    "        #dp[i][j-1]\n",
    "        #dp[i-1][j-1]\n",
    "        #完全想不出一个状态转换方程，因为我不知道剩下的空白专的位置，无法延伸做\n",
    "        #为什么看了答案之后觉得这么简单呢，卧槽\n",
    "        #写一写吧\n",
    "        n = len(floor)\n",
    "\n",
    "        dp = [ [0 for i in range(numCarpets+1)] for i in range(n+1)]\n",
    "\n",
    "        for i in range(1,1+n,1):\n",
    "            dp[i][0] = dp[i-1][0] + (floor[i-1] == '1')\n",
    "\n",
    "        for j in range(1,1+numCarpets,1):\n",
    "            for i in range(1,1+n,1):\n",
    "                color = floor[i-1]\n",
    "                a = 0 if color == '0' else 1\n",
    "                b = i - carpetLen if i >= carpetLen else 0\n",
    "                #这些数据要实现0的突破必须要从第二个入手，不然0会一直传导到最末尾\n",
    "                #dp[4][1] = min(dp[3][1]+1,dp[2][0])\n",
    "                # if (i==4 and j==1):\n",
    "                #     print(dp[i][j] ,dp[i-1][j] + a ,dp[b][j-1])\n",
    "                dp[i][j] = min(dp[i-1][j] + a, dp[b][j-1])\n",
    "        #print(dp)\n",
    "        return dp[n][numCarpets]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n=len(floor)\n",
    "        if n<=numCarpets*carpetLen:\n",
    "            return 0\n",
    "        dp=[[float(\"inf\") for _ in range(numCarpets+1)]for _ in range(n+1)]\n",
    "        for i in range(numCarpets+1):\n",
    "            dp[0][i]=0\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=copy.deepcopy(dp[i-1])\n",
    "            if floor[i-1]==\"0\":\n",
    "                continue\n",
    "            for j in range(numCarpets+1):\n",
    "                dp[i][j]=dp[i-1][j]+1\n",
    "                if j>0:\n",
    "                    dp[i][j]=min(dp[i][j],dp[max(0,i-carpetLen)][j-1])\n",
    "        #print(dp)\n",
    "        return min(dp[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        dp = [[1] + [0]*(n-1) for _ in range(numCarpets+1)]\n",
    "        dp[0][0] = int(floor[0] == '0')\n",
    "        for i in range(1, n):\n",
    "            dp[0][i] = dp[0][i-1] + (floor[i] == '0')\n",
    "        for i in range(1, numCarpets+1):\n",
    "            for j in range(1, n):\n",
    "                if j >= carpetLen:\n",
    "                    dp[i][j] = max(dp[i-1][j-carpetLen] + carpetLen, dp[i][j-1]+dp[0][j]-dp[0][j-1])\n",
    "                else:\n",
    "                    dp[i][j] = j+1\n",
    "        return n - dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        floor = list(map(int,floor))\n",
    "        pref = [0] + list(accumulate(floor))\n",
    "        if numCarpets * carpetLen >= n: return 0\n",
    "        @cache\n",
    "        def dfs(i,left):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            if floor[i]==0:\n",
    "                return dfs(i+1,left)\n",
    "            else:\n",
    "                return max(dfs(i+1,left), dfs(i+carpetLen,left-1)+pref[min(i+carpetLen, n)] - pref[i] if left else -inf)\n",
    "        res = dfs(0,numCarpets)\n",
    "        dfs.cache_clear()\n",
    "        return pref[-1] - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, remain: int) -> int:\n",
    "            # 每个位置跳还是不跳\n",
    "            if index >= n or remain == 0:\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            res = (\n",
    "                max(res, dfs(index + carpetLen, remain - 1))\n",
    "                + preSum[min(index + carpetLen, n)]\n",
    "                - preSum[index]\n",
    "            )\n",
    "            res = max(res, dfs(index + 1, remain))\n",
    "            return res\n",
    "\n",
    "        n = len(floor)\n",
    "        nums = [1 if floor[i] == '1' else 0 for i in range(n)]\n",
    "        preSum = [0] + list(accumulate(nums))\n",
    "        res = dfs(0, numCarpets)\n",
    "        dfs.cache_clear()\n",
    "        return floor.count('1') - res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, a: str, b: int, c: int) -> int:\n",
    "        n = len(a)\n",
    "        a = [j for j in range(n) if a[j]=='1']\n",
    "        if not a:\n",
    "            return 0\n",
    "        n = len(a)\n",
    "        if not b:\n",
    "            return n\n",
    "        @cache  \n",
    "        def f(j, x):\n",
    "            if j>=n:\n",
    "                return 0\n",
    "            if x==0:\n",
    "                return 0 \n",
    "            i = bisect_left(a, a[j]+c)\n",
    "            return max(f(j+1, x), i-j+f(i, x-1))\n",
    "        ans = f(0, b)\n",
    "        f.cache_clear() \n",
    "        return n-ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return floor[:i + 1].count('1')\n",
    "            if k*carpetLen >= i + 1:\n",
    "                return 0\n",
    "            if floor[i] == '0':\n",
    "                return dfs(i - 1,k)\n",
    "            return min(1 + dfs(i - 1,k),dfs(i - carpetLen,k - 1))\n",
    "        return dfs(len(floor) - 1,numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if floor[i] == '0':\n",
    "                return dfs(i - 1, j)\n",
    "            if j > 0:\n",
    "                return min(dfs(i - carpetLen, j - 1), dfs(i - 1, j) + 1)\n",
    "            return dfs(i - 1, j) + 1\n",
    "        n = len(floor)\n",
    "        return dfs(n - 1, numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,k):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return floor[:i + 1].count('1')\n",
    "            \n",
    "            if floor[i] == '0':\n",
    "                return dfs(i - 1,k)\n",
    "            return min(1 + dfs(i - 1,k),dfs(i - carpetLen,k - 1))\n",
    "        return dfs(len(floor) - 1,numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        floor = list(map(int,floor))\n",
    "        pref = [0] + list(accumulate(floor))\n",
    "        if numCarpets * carpetLen >= n: return 0\n",
    "        @cache\n",
    "        def dfs(i,left):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            if floor[i]==0:\n",
    "                return dfs(i+1,left)\n",
    "            else:\n",
    "                return max(dfs(i+1,left), dfs(i+carpetLen,left-1)+pref[min(i+carpetLen, n)] - pref[i] if left else -inf)\n",
    "        dfs.cache_clear()\n",
    "        return pref[-1] - dfs(0,numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        floor = list(map(int,floor))\n",
    "        pref = [0] + list(accumulate(floor))\n",
    "        if numCarpets * carpetLen >= n: return 0\n",
    "        @cache\n",
    "        def dfs(i,left):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            if floor[i]==0:\n",
    "                return dfs(i+1,left)\n",
    "            else:\n",
    "                return max(dfs(i+1,left), dfs(i+carpetLen,left-1)+pref[min(i+carpetLen, n)] - pref[i] if left else -inf)\n",
    "        \n",
    "        return pref[-1] - dfs(0,numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        if numCarpets * carpetLen >= n:\n",
    "            return 0\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            presum[i + 1] = presum[i]\n",
    "            if floor[i] == '1':\n",
    "                presum[i + 1] += 1\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, k) -> int:\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "\n",
    "            # 不覆盖\n",
    "            ans = max(ans, dfs(i - 1, k))\n",
    "\n",
    "            # 覆盖 [i-carpetLen+1, i]这块区间\n",
    "            l = max(i - carpetLen + 1, 0)\n",
    "            ans = max(ans, dfs(i - carpetLen, k - 1) + presum[i + 1] - presum[l])\n",
    "\n",
    "            return ans\n",
    "        return presum[-1] - dfs(n - 1, numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            f[i + 1] = f[i] + (floor[i] == '1')\n",
    "        @cache\n",
    "        def dfs(i, k) -> int:\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return f[i + 1]\n",
    "            ans = n + 1\n",
    "\n",
    "            # 不覆盖\n",
    "            ans = min(ans, dfs(i - 1, k) + (floor[i] == '1'))\n",
    "\n",
    "            # 覆盖 [i-carpetLen+1, i]这块区间\n",
    "            ans = min(ans, dfs(i - carpetLen, k - 1))\n",
    "\n",
    "            return ans\n",
    "        return dfs(n - 1, numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,re):\n",
    "            if i >= len(floor): return 0\n",
    "            if floor[i] == '0':return dfs(i+1,re)\n",
    "            if re == 0: return 1 + dfs(i+1,re)\n",
    "            return min(1 + dfs(i+1,re),dfs(i+carpetLen,re-1))\n",
    "        return dfs(0,numCarpets)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i >= len(floor): return 0\n",
    "            if floor[i] == '0':\n",
    "                return dfs(i + 1, c)\n",
    "            minl = dfs(i + 1, c) + 1\n",
    "            if c > 0:\n",
    "                minl = min(minl, dfs(i + carpetLen, c - 1))\n",
    "            return minl\n",
    "        return dfs(0, numCarpets)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        floor = list(map(int,floor))\n",
    "        pref = [0] + list(accumulate(floor))\n",
    "        @cache\n",
    "        def dfs(i,left):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            if floor[i]==0:\n",
    "                return dfs(i+1,left)\n",
    "            else:\n",
    "                return max(dfs(i+1,left), dfs(i+carpetLen,left-1)+pref[min(i+carpetLen, n)] - pref[i] if left else -inf)\n",
    "        \n",
    "        return pref[-1] - dfs(0,numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        floor = list(map(int,floor))\n",
    "        pref = [0] + list(accumulate(floor))\n",
    "        if pref[-1] == 0:\n",
    "            return 0\n",
    "        @cache\n",
    "        def dfs(i,left):\n",
    "            if i>=n:\n",
    "                return 0\n",
    "            if floor[i]==0:\n",
    "                return dfs(i+1,left)\n",
    "            else:\n",
    "                return max(dfs(i+1,left), dfs(i+carpetLen,left-1)+pref[min(i+carpetLen, n)] - pref[i] if left else -inf)\n",
    "        \n",
    "        return pref[-1] - dfs(0,numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        arr = [0] * n\n",
    "        arr[n - 1] = 1 if floor[n - 1] == '1' else 0\n",
    "        for i in range(n - 2,-1,-1) :\n",
    "            arr[i] = arr[i + 1]\n",
    "            if floor[i] == '1' :\n",
    "                arr[i] += 1\n",
    "        @cache\n",
    "        def dfs(i,num) :\n",
    "            if i >= n :\n",
    "                return 0\n",
    "            if num == 0 :\n",
    "                return arr[i]\n",
    "            not_cover = 1 if floor[i] == '1' else 0\n",
    "            res = min(dfs(i + 1,num) + not_cover, dfs(i + carpetLen, num - 1))\n",
    "            return res\n",
    "\n",
    "        return dfs(0,numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        presum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            presum[i + 1] = presum[i]\n",
    "            if floor[i] == '1':\n",
    "                presum[i + 1] += 1\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, k) -> int:\n",
    "            if k == 0:\n",
    "                return 0\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "\n",
    "            # 不覆盖\n",
    "            ans = max(ans, dfs(i - 1, k))\n",
    "\n",
    "            # 覆盖 [i-carpetLen+1, i]这块区间\n",
    "            l = max(i - carpetLen + 1, 0)\n",
    "            ans = max(ans, dfs(i - carpetLen, k - 1) + presum[i + 1] - presum[l])\n",
    "\n",
    "            return ans\n",
    "        return presum[-1] - dfs(n - 1, numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, m: int, c: int) -> int:\n",
    "        \n",
    "        n = len(floor)\n",
    "        pre = list(accumulate([int(w) for w in floor], initial=0))\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, x):\n",
    "            if i >= n:\n",
    "                return 0\n",
    "            if not x:\n",
    "                return pre[-1] - pre[i]\n",
    "            res = int(floor[i]) + dfs(i+1, x)\n",
    "            if x:\n",
    "                cur = dfs(i+c, x-1)\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        n = len(floor)\n",
    "        @cache\n",
    "        def dfs(i,num) :\n",
    "            if i >= n :\n",
    "                return 0\n",
    "            not_cover = 1 if floor[i] == '1' else 0\n",
    "            if num == 0 :\n",
    "                return dfs(i + 1,num) + not_cover\n",
    "            res = min(dfs(i + 1,num) + not_cover, dfs(i + carpetLen, num - 1))\n",
    "            return res\n",
    "\n",
    "        return dfs(0,numCarpets)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n",
    "        # 1 <= carpetLen <= floor.length <= 1000 ;; 1 <= numCarpets <= 1000\n",
    "        \n",
    "        @cache\n",
    "        def f(i, k):\n",
    "            if i >= len(floor):\n",
    "                return 0\n",
    "            ans = int(floor[i]) + f(i+1, k)\n",
    "            if k > 0:\n",
    "                ans = min(ans, f(i+carpetLen, k-1))\n",
    "            return ans\n",
    "        \n",
    "        return f(0, numCarpets)\n",
    "        \n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
